package com.imooc.distributedemo.resume.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * leetcode139 单词拆分
 */
public class Solution139 {

    public static void main(String[] args) {
        String s = "leetcode";
        List<String> words = new ArrayList<>();
        words.add("leet");
        words.add("code");
        /*boolean r = wordBreak(s,words);*/
        /*String s = "abcd";
        List<String> result = getSubsets(s);
        System.out.println("Subsets of " + s + ":");
        for (String subset : result) {
            System.out.println(subset);
        }*/

        Set<String> b = getAll(s,words);
        System.out.println(b);
    }

    private static Set<String> getAll(String s, List<String> words) {
        Set<String> list = new HashSet<>();

        for (int i = 1; i < s.length(); i++) {
            if(i==s.length()-1){
                System.out.println("dddddddddddddd");
            }
            for (int j = i; j >= 0; j--) {
                String tmp;
                if(j==0&&i==1){
                    tmp = s.substring(j,i);
                }else{
                    tmp = s.substring(j,i+1);
                }

                if("".equals(tmp)||null==tmp){
                    continue;
                }
                list.add(tmp);
            }
            System.out.println("round"+i+"[start]"+s.charAt(i));
            System.out.println(list);
            System.out.println("=================");
        }

        return list;
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        if("".equals(s) || null == s){
            return false;
        }
        if(wordDict==null||wordDict.size()<1){
            return false;
        }

//        boolean[] dp = new boolean[s.length()+1];
//        dp[0]=true;
        List<Boolean> list = new ArrayList<>(wordDict.size());
//        for(String str:wordDict){
//            list.add(Boolean.FALSE);
//        }
        for (int i = 1; i < s.length(); i++) {
            for (int j = i-1; j >=0; j--) {
                String tmp = s.substring(j,i);
                if(wordDict.contains(tmp)){
                    System.out.println(tmp);
                    list.add(true);
                }
            }
        }
        boolean result = list.size()>=wordDict.size();
        return result;
    }

    // 生成字符串的所有子集
    public static List<String> getSubsets(String s) {
        List<String> subsets = new ArrayList<>();
        int n = s.length();
        // 2^n 个子集，包括空集
        for (int i = 0; i < (1 << n); i++) {
            // 构建子集
            StringBuilder subset = new StringBuilder();
            for (int j = 0; j < n; j++) {
                // 如果位i的第j位为1，则选择s的第j个字符
                if ((i & (1 << j)) != 0) {
                    subset.append(s.charAt(j));
                }
            }
            subsets.add(subset.toString());
        }
        return subsets;
    }
}
